'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-06-24 14:29:20
'''
'''
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
#暴力三重循环最容易想到，不过会超出时间限制。
class Solution:
    def threeSumClosest(self, nums, target) -> int:
        import sys
        best = sys.maxsize

        def update(s):
            nonlocal best
            if abs(s-target)<abs(best-target):
                best = s

        nums.sort() # 排序之后，采用双指针。
        for i, v in enumerate(nums[:-2]):  #对第一重循环，不能避免。
            if i>=1 and v == nums[i-1]:
                continue
            head = i+1
            tail = len(nums)-1
            while head<tail: #双指针解法，这里可以用二分嘛？好像不行。
                s = v + nums[head] + nums[tail]
                if s == target:
                    return s
                update(s)
                if s<target:
                    head += 1
                    while head <len(nums) and nums[head] == nums[head-1]:
                        head += 1
                else:
                    tail -= 1
                    while tail >0 and nums[tail] == nums[tail+1]:
                        tail -= 1
        return best

                    

if __name__ == "__main__":
    solution = Solution()
    nums = [-1,2,1,-4]
    target = 1
    solution.threeSumClosest(nums, target)